package com.kobe.game_60;

import com.kobe.util.MathUtil;

/**
 * 
 * There are exactly ten ways of selecting three from five, 12345:
 * 
 * 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
 * 
 * In combinatorics, we use the notation, ^(5)C_(3) = 10.
 * 
 * In general, ^(n)C_(r) = n!
 * 
 * r!(n−r)! ,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.
 * 
 * It is not until n = 23, that a value exceeds one-million: ^(23)C_(10) =
 * 1144066.
 * 
 * How many, not necessarily distinct, values of ^(n)C_(r), for 1 ≤ n ≤ 100, are
 * greater than one-million?
 * 
 * 
 */
public class _53 {

    /**
     * 
     * tuned for different situation.
     * 
     */
    private static double C(int n, int r) {
        if (r < n / 2) {
            return MathUtil.getFactorial(n - r + 1, n)/ MathUtil.getFactorial(r);
        } else {
            return MathUtil.getFactorial(r + 1, n) / MathUtil.getFactorial(n - r);
        }
    }

    public static void main(String[] args) {
        int result = 0,total=0;
        long begin = System.currentTimeMillis();
        for (int n = 1; n <= 100; n++) {
            total += n + 1;
            for (int r = 0; r <= n; r++) {
                if (C(n, r) > 1000000) {
                    r = n - r;
                } else {
                    result++;
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println(end - begin);
        System.out.println(total - result);
    }
}
